#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<iostream>

using namespace std;


template<typename E>
//qsort is also a function in Linux
class QSortITA
{
public:
	QSortITA(E datalist[], int size)
	{
		dataArray = datalist;
		performQSort(0, size - 1);
	}

	void performQSort(int leftindex, int rightindex)
	{
		if (leftindex >= rightindex)
			return;

		int q = partition(leftindex, rightindex);
		performQSort(leftindex, q - 1);
		performQSort(q + 1, rightindex);
	}//end constructor

private:
	E * dataArray;

	void swap(int indexSt, int indexTg)
	{
		E temp = dataArray[indexSt];
		dataArray[indexSt] = dataArray[indexTg];
		dataArray[indexTg] = temp;
	}//end function: Swap elements.

	inline int partition(int leftindex, int rightindex)
	{
		E temp = dataArray[rightindex];
		int tempindex = leftindex - 1;
		for (int index = leftindex; index < rightindex; index++)
		{
			if (dataArray[index] < temp)
			{
				tempindex = tempindex + 1;
				swap(tempindex, index);
			}//end if			
		}//end loop: Find all the elements < array[rightindex]
		swap(tempindex + 1, rightindex);

		return tempindex + 1;
	}//end function

};//end class: Quicksort. 